//给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 
//
// 每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处: 
//
// 
// 0 <= j <= nums[i] 
// i + j < n 
// 
//
// 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [2,3,1,1,4]
//输出: 2
//解释: 跳到最后一个位置的最小跳跃数是 2。
//     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
// 
//
// 示例 2: 
//
// 
//输入: nums = [2,3,0,1,4]
//输出: 2
// 
//
// 
//
// 提示: 
//
// 
// 1 <= nums.length <= 10⁴ 
// 0 <= nums[i] <= 1000 
// 题目保证可以到达 nums[n-1] 
// 
//
// Related Topics 贪心 数组 动态规划 👍 2753 👎 0

package com.rpocky.leetcode.editor.cn;

//Java：跳跃游戏 II
public class P45JumpGameIi {
    public static void main(String[] args) {
        // TO TEST
        Solution solution = new P45JumpGameIi().new Solution();
        System.out.println(solution.jump(new int[]{1, 2, 1, 1, 1, 4, 4, 1, 5, 2, 3, 4, 1, 4, 2, 5, 2, 6, 4, 4, 2, 2, 5, 6, 2, 3, 4, 5, 4, 4, 2, 3, 1, 4, 1, 6, 2, 3, 5, 3, 6, 6, 1, 2, 5, 3, 3, 4, 6, 1, 1, 5, 3, 3, 4, 5, 1, 4, 2, 6, 6, 4, 1, 4, 1, 2, 1, 4, 4, 2, 1, 2, 2, 5, 6, 5, 4, 4, 3, 6, 5, 2, 5, 6, 1, 4, 3, 4, 3, 3, 1, 2, 6, 5, 3, 6, 1, 2, 6, 4, 2, 3, 3, 4, 6, 3, 5, 3, 2, 3, 3, 1, 3, 2, 4, 1, 3, 5, 1, 1, 5, 2, 4, 2, 2, 5, 3, 4, 2, 1, 3, 3, 1, 2, 4, 5, 4, 6, 2, 5, 6, 4, 6, 5, 2, 2, 1, 4, 6, 4, 2, 4, 1, 6, 3, 3, 6, 1, 4, 5, 4, 5, 1, 2, 3, 6, 1, 4, 3, 2, 5, 1, 5, 2, 5, 1, 2, 3, 3, 6, 6, 3, 5, 2, 6, 1, 6, 4, 3, 4, 1, 2, 5, 1, 5, 6, 5, 3, 1, 5, 6, 3, 6, 3, 5, 6, 2, 2, 6, 3, 4, 1, 4, 1, 1, 3, 4, 1, 5, 6, 5, 4, 2, 5, 3, 6, 4, 1, 2, 3, 5, 6, 5, 2, 3, 6, 1, 3, 4, 6, 3, 2, 5, 5, 1, 6, 6, 6, 2, 3, 5, 5, 4, 5, 2, 1, 6, 6, 2, 5, 1, 3, 2, 5, 1, 2, 3, 4, 1, 1, 5, 1, 4, 1, 2, 2, 6, 1, 4, 3, 2, 1, 6, 5, 1, 6, 2, 3, 5, 3, 6, 6, 5, 2, 1, 4, 4, 5, 3, 5, 5, 1, 3, 2, 6, 1, 6, 6, 4, 6, 5, 3, 3, 1, 6, 2, 6, 4, 2, 4, 1, 2, 2, 2, 2, 1, 5, 4, 3, 6, 3, 2, 5, 5, 4, 6, 4, 1, 5, 2, 4, 6, 2, 4, 5, 5, 3, 4, 6, 6, 1, 6, 6, 5, 3, 1, 4, 6, 5, 3, 5, 3, 5, 2, 3, 4, 6, 2, 5, 6, 6, 2, 5, 6, 1, 1, 5, 4, 5, 6, 6, 5, 5, 3, 3, 4, 4, 5, 2, 6, 5, 1, 3, 2, 3, 1, 3, 1, 2, 3, 5, 2, 5, 3, 2, 2, 3, 4, 4, 2, 6, 5, 1, 3, 4, 6, 1, 6, 4, 4, 2, 4, 5, 2, 5, 6, 6, 1, 3, 1, 1, 4, 6, 5, 6, 4, 1, 3, 1, 1, 6, 2, 6, 4, 5, 5, 3, 5, 3, 6, 6, 2, 1, 3, 2, 5, 5, 3, 5, 3, 3, 5, 3, 2, 1, 2, 2, 6, 1, 6, 4, 2, 2, 2, 6, 2, 4, 2, 5, 5, 2, 3, 1, 1, 5, 6, 6, 3, 4, 6, 2, 1, 2, 1, 4, 2, 5, 6, 5, 5, 3, 2, 1, 5, 1, 3, 2, 2, 5, 1, 6, 1, 6, 5, 6, 2, 6, 3, 6, 5, 1, 4, 6, 3, 3, 6, 6, 4, 1, 4, 6, 3, 4, 1, 4, 2, 5, 5, 5, 4, 2, 5, 6, 6, 3, 1, 5, 4, 2, 3, 6, 1, 6, 4, 1, 5, 5, 6, 4, 5, 4, 4, 6, 5, 2, 5, 1, 4, 3, 2, 6, 1, 5, 2, 6, 2, 6, 1, 2, 3, 5, 5, 4, 4, 5, 4, 2, 1, 4, 1, 4, 6, 1, 1, 2, 6, 2, 3, 6, 4, 4, 5, 6, 6, 4, 1, 6, 3, 2, 4, 1, 4, 5, 5, 2, 6, 6, 4, 2, 5, 4, 6, 6, 5, 2, 4, 1, 1, 4, 1, 1, 4, 6, 1, 5, 2, 4, 6, 5, 1, 6, 6, 6, 2, 1, 6, 1, 5, 5, 4, 5, 2, 3, 2, 2, 2, 6, 4, 6, 2, 4, 6, 4, 5, 1, 3, 2, 4, 2, 6, 6, 4, 3, 3, 1, 1, 4, 4, 5, 5, 4, 1, 6, 5, 1, 3, 3, 6, 5, 5, 3, 6, 3, 5, 2, 4, 3, 4, 6, 5, 2, 6, 6, 1, 2, 3, 4, 6, 1, 5, 6, 4, 6, 6, 1, 1, 2, 4, 6, 4, 1, 1, 6, 6, 2, 1, 1, 2, 3, 6, 5, 3, 1, 6, 1, 3, 6, 2, 4, 5, 3, 2, 5, 3, 5, 5, 2, 1, 3, 4, 4, 6, 2, 4, 3, 3, 1, 5, 3, 3, 1, 2, 5, 2, 5, 2, 2, 4, 2, 2, 4, 6, 3, 1, 4, 2, 3, 4, 2, 2, 6, 3, 2, 6, 3, 3, 5, 5, 5, 2, 3, 1, 6, 5, 4, 5, 2, 6, 5, 2, 1, 2, 2, 2, 2, 2, 3, 2, 6, 3, 1, 5, 6, 1, 4, 6, 5, 3, 3, 5, 5, 6, 5, 1, 4, 3, 5, 5, 3, 4, 6, 4, 6, 3, 2, 1, 1, 6, 2, 2, 5, 5, 3, 1, 3, 5, 6, 3, 6, 2, 5, 6, 2, 1, 4, 4, 2, 2, 6, 2, 1, 5, 6, 1, 1, 3, 3, 5, 5, 3, 2, 5, 2, 1, 3, 2, 4, 3, 5, 2, 5, 5, 4, 1, 1, 3, 4, 3, 1, 3, 5, 5, 4, 5, 5, 1, 3, 5, 4, 6, 5, 4, 2, 1, 2, 6, 6, 4, 4, 5, 6, 6, 6, 3, 4, 3, 5, 2, 5, 6, 5, 2, 1, 4, 5, 3, 1, 6, 4, 1, 5, 4, 5, 2, 5, 1, 4, 2, 6, 3, 3, 5, 1, 3, 4, 3, 3, 6, 6, 5, 5, 5, 4, 5, 3, 6, 6, 6, 4, 2, 4, 4, 1, 2, 2, 2, 3, 2, 2, 5, 6, 5, 6, 3, 3, 1, 1, 4, 1, 6, 6, 5, 3, 2, 6, 5, 2, 1, 6, 1, 4, 6, 4, 1, 2, 1, 2, 5, 1, 1, 6, 3, 2, 5, 4, 5, 2, 6, 5, 6, 2, 2, 1, 5, 5, 1, 6, 2, 1, 3, 4, 5, 4, 3, 1, 5, 6, 5, 4, 1, 2, 3, 4, 2, 2, 6, 2, 4, 3, 2, 5, 3, 2, 2, 5, 6, 3, 3, 2, 1, 4, 5, 2, 3, 2, 5, 3, 1, 3, 6, 3, 6, 4, 2, 5, 3, 6, 1, 6, 5, 2, 1, 5, 2, 1, 1, 4, 3, 3, 1, 1, 2, 2, 1, 1, 4, 1, 6, 5, 5, 6, 4, 6, 6, 2, 2, 2, 6, 1, 1, 1, 1, 5, 2, 2, 1, 6, 5, 6, 1, 3, 1, 6, 4, 1, 2, 1, 5, 1, 1, 3, 6, 4, 5, 4, 2, 3, 4, 1, 5, 2, 2, 1, 6, 2, 3, 2, 3, 3, 1, 1, 4, 5, 5, 3, 5, 3, 6, 4, 5, 4, 4, 4, 2, 2, 1, 4, 6, 0, 0, 0, 0, 0}));
        System.out.println(solution.jump(new int[]{0}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
//        private final int[] dp = new int[11000]; // 到达i下标的最小步数
//
//        private void init() {
//            dp[0] = 0; // 起点直接到达，步数为0
//            for (int i = 1; i < 11000; i++) {
//                // 设置为最大值
//                dp[i] = 0x3f3f3f3f;
//            }
//        }
//
//        public int jump(int[] nums) {
//            init();
//            for (int i = 0; i < nums.length; i++) {
//                // nums[i]为i处能跳的**最大**长度，所以需要遍历所有能跳的长度
//                for (int jumpLen = 0; jumpLen <= nums[i]; jumpLen++) {
//                    // 跳到的位置的 到达该位置最小步数 = 原本的值 和 从i处再用一步跳过去的值 的 较小者
//                    dp[i + jumpLen] = Integer.min(dp[i + jumpLen], dp[i] + 1);
//                }
//            }
//            return dp[nums.length - 1];
//        }

        // 因为nums[i]代表的是能跳的最大长度而不是指定长度，所以可以想简单点
        // 直接使用贪心，在处于下标i时能跳到的范围里选择跳到一个能到达最远的下标处
        public int jump(int[] nums) {
            int count = 0; // 总步数
            int right = 0; // 右边界
            int maxIndex = 0; // 此次能跳到的最远下标
            // 注意，要 <nums.length-1，即如果已经到达 nums.length-1 下标，不用再进入循环继续计算步数
            for (int i = 0; i < nums.length - 1; i++) {
                // i到达右边界前，一直更新该范围内能跳到的最远下标
                maxIndex = Math.max(maxIndex, i + nums[i]);
                if (i == right) {
                    // 遍历到右边界了，更新跳到的最远下标为新的右边界
                    // 这就是i这个下标能跳的下标范围里，所有下标中跳的最远的位置
                    right = maxIndex;
                    // 跳过去（注意，这里是跳到能够到达新右边界的某个下标处，不是跳到新右边界！）
                    count++;
                    // 下次循环会接着继续遍历nums，在上次的边界和新边界之间找到跳的最远的下标
                }
            }
            return count;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
